package leetcode.editor.cn.dsa20_heap;
//给定两个以升序排列的整形数组 nums1 和 nums2, 以及一个整数 k。
// 定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2。
// 找到和最小的 k 对数字 (u1,v1), (u2,v2) ... (uk,vk)。
//
// 示例 1: 
// 输入: nums1 = [1,7,11], nums2 = [2,4,6], k = 3
//输出: [1,2],[1,4],[1,6]
//解释: 返回序列中的前 3 对数：
//     [1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]
// 
// 示例 2:
// 输入: nums1 = [1,1,2], nums2 = [1,2,3], k = 2
//输出: [1,1],[1,1]
//解释: 返回序列中的前 2 对数：
//     [1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]
//
// 示例 3: 
// 输入: nums1 = [1,2], nums2 = [3], k = 3
//输出: [1,3],[2,3]
//解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
// 
// Related Topics 堆 
// 👍 143 👎 0


import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class FindKPairsWithSmallestSums373 {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        // 自定义类：存储两个数组的一对值
        class Pair {
            int x;
            int y;
            public Pair(int x, int y) {
                this.x = x;
                this.y = y;
            }
        }
        // 定义比较器：Comparator
        class Sort implements Comparator<Pair> {
            @Override
            public int compare(Pair o1, Pair o2) {
                // 重写排序方法，按照和的升序排列
                return o1.x + o1.y - o2.x - o2.y;
            }
        }
        public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
            List<List<Integer>> result = new ArrayList<>();
            if (nums1.length == 0 || nums2.length == 0) return result;
            int min1 = Math.min(nums1.length, k);
            int min2 = Math.min(nums2.length, k);
            // 存储所有数字对组合
            Pair[] arr = new Pair[min1 * min2];
            int index = 0;
            for (int i = 0; i < min1; i++) {
                for (int j = 0; j < min2; j++) {
                    arr[index++] = new Pair(nums1[i], nums2[j]);
                }
            }
            // 按和大小进行升序排列
            Arrays.sort(arr, new Sort());
            // 取出和最小的k对数字
            for (int i = 0; i < Math.min(arr.length, k); i++) { // 考虑k特别大的情况
                List<Integer> temp = new ArrayList<>(2);
                temp.add(arr[i].x);
                temp.add(arr[i].y);
                result.add(temp);
            }
            return result;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}